[백준 16236] 아기 상어

[ 백준 16236 : 아기 상어 ]

2018 삼성전자 sw직무 하반기 기출문제입니다.

역대 삼성전자 기출문제가 그렇듯 역시나 BFS,DFS,완탐,DP,단순구현 입니다.

저는 문제를 단순히 BFS로 풀어갔습니다. 조건만 잘 지킨다면 한번에 답이나오는 문제로
입력값의 범위도 작아서 별로 생각할 것이 없습니다. 길면 40분? 짧으면 15분이나 20분에 끝낼만한 문제라고 생각합니다.

일단 구조체로 상어의 정보를 입력합니다. 좌표,먹은 물고기갯수,상어 크기.
그리고 BFS를 이용해 현재 상어의 좌표에서 물고기들마다의 좌표와 거리를 계산합니다.
거리가 같다면 X의 좌표가 더 작은것
거리가 같고 X의 좌표가 같다면 Y의 좌표가 더 작은것

이렇게 결과 좌표와 거리를 갱신해 나가면서 큐에 아무것도 남지않아 BFS탐색을 완료한 후

상어구조체의 값들을 갱신합니다. 갱신된 좌표, 물고기갯수++,상어크기(조건)
그리고 갱신된 거리를 답에 더해줍니다.

상어가 더이상 이동하지 못한다면 더해진 답을 출력한 후 프로그램을 종료하면 됩니다.

[백준 16235] 나무 재테크

[ 백준 16235 : 나무 재테크 ]

2018 삼성전자 sw직무 하반기 기출문제 입니다.
문제는 단순 구현에 소팅을 어떤식으로 진행하는지가 관건이 되는 문제 같습니다.
역시나 이문제도 역대 삼성전자 기출문제처럼 조건을 빼먹지 않고 구현을 하면 되는 문제입니다.

저는 (봄,여름) (가을) (겨울) 이런식으로 함수를 짜서 k만큼 반복을 해서 마지막에 살아있는 나무들의 갯수를 셌는데
이차원 벡터에 나무를 직접 심어주고 죽여주고 이런식으로 진행했습니다.


봄에는 무조건 양분이 나무의 나이만큼 있으면 나무의 나이를 ++ 해주고 양분의 양을 나무 나이만큼 - 해줍니다.
그리고 나무의 나이가 5로 나누어떨어지는지를 여기서 체크를 미리해 5로 나누어 떨어진다면 큐에 집어넣어줍니다.
또한, 나무의 나이만큼 양분이 없다면 그 이후로는 벡터에 있는 값들을 pop_back해가면서 나이/2 만큼 양분에 더해줍니다.

이렇게 봄,여름 과정을 끝내고 가을 함수를 준비합니다.
가을에는 큐에 집어넣은 나무들을 BFS알고리즘을 이용해 주위 8방향으로 번식시킵니다.
겨울에는 처음 입력한 양분만큼 더해주는데 이걸 봄 여름과정에서 해도 될듯합니당.


그냥 k만큼 반복한 후의 이차원 벡터의 크기가 답이 됩니다.

[백준 16234] 인구 이동

[ 백준 16234 : 인구 이동 ]

요번 삼성전자 2018 하반기 sw기출문제 입니다. 오전 시간에 나왔던 문제라고 하네요.

지금까지 삼성전자 기출문제들을 살펴보면 대체로 bfs, dfs, 완전탐색, dp로 나뉘는데 이것도 역시 그 범주안에 들어가는것 같네요.

3시간에 두문제니까 한문제당 1시간 30분씩만 풀어도 충분한... 아마 대부분 30분안에들 푸셨을 것으로 예상됩니다.
따로 복잡한건 없고 문제에 나온 그대로 구현만 시켜주면되기 때문에 시간이 오래 걸릴것같진 않습니다.

제가 푼 로직은

1. 입력
2. CHK변수를 통해 인구가 이동하지 않으면 프로그램을 끝냅니다.
3. DFS를 통해 한 컴포넌트의 국가 갯수와 인구의 합을 리턴합니다.
4. 큐에 좌표와 컴포넌트 인덱스를 집어넣어 국가들의 인구수를 맞춰줍니다.

큐와 재귀를 이용해 풀었는데 뭐 어떻게 구현하던 시간이나 메모리에서 에러가 뜰 법한 문제는 아니라서 다들 쉽게 구현했을것같습니다.

[백준 5213] 과외맨

[ 백준 5213 : 과외맨 ]

BFS + DFS 를 이용하는 문제

일단 맵이 정말 특이하게 생겼다. 보통 보던 N*M의 직사각형의 모양이 아니라 짝수번째 행은 맨 처음과 마지막 열이 비어있다.

문제를 풀 때 고려할 것은 이것 뿐인것같다.

처음 0,0에서 출발해서 상하좌우를 체크하며 돌아다니는 것은 BFS를 이용했고,
문제의 답을 출력해야하는 경로와 지나온 칸의 수는 DFS를 이용했다.

일단 문제에서 그려진대로 똑같이 맵을 만들었다. 삼차원배열로 맵을 입력받았는데
MAT이라는 변수의 [0][X좌표][Y좌표] 는 입력하는 값들, 그리고 [1][X][Y]에는 해당 맵의 숫자를 입력했다.
내가 만든 맵은 0행0열부터 시작하므로 짝수행은 0~2*N-1까지 열이 존재하고 홀수행은 1~2*N-2까지 열이 존재한다.
홀수행과 짝수행은 ( 행&1 )으로 쉽게 구할 수 있다.

그리고 마지막 경로를 DFS로 탐색하기 위해 해당 번호마다 지나온 번호를 입력했고,
한번 탐색했던곳을 쓸모없이 다시 탐색하지 않기 위해서 지나온 좌표마다 그때까지 이동한 순서를 넣어줬다.
이 처리를 함으로써 한 번 지나왔지만 만약 그곳을 3번만에 왔고, 지금은 2번만에 그곳을 가는 것이라면 해당 좌표를 큐에 넣는 식으로 구현했다.
또 하나의 처리를 더해줬는데,
맵의 한 번호마다 두개의 좌표가 달려있어 이를 묶어서 처리하기 위해 (VI[500*500]) 변수를 설정해 몇번만에 그 번호로 왔는지를 저장했다.

따라서
이차원 배열로 해당 좌표까지 얼마만에 왔는지, 일차원 배열로 해당 번호까지 얼마만에 왔는지, 일차원 배열로 지나온 좌표를 저장.
이런식으로 구현했다.

[백준 11501] 주식

[ 백준 11501 : 주식 ]

그리디 문제였다.
생각만 하면 쉬운 문제라고 생각한다. 처음에 dp인가? 라고 생각하면서 테스트 케이스를 하나씩 풀어보다가 그냥 단순하게 풀 수 있겠다 싶어서
제출 했는데 맞았습니다! 가 떠서 으음! 다행이다

idx라는 변수에 배열의 가장 마지막 값을 입력한다.
그리고 배열을 뒤에서부터 탐색하면서 만약 현재 탐색하고 있는 값이 idx보다 크다면 idx에 배열의 값을 넣는다.
만약 idx보다 작다면 idx에서 탐색하는 값을 뺀 값을 답으로 출력할 변수에 더한다.

[백준 9376] 탈옥

[ 백준 9376 : 탈옥 ]

bfs를 응용한 문제.

꽤 생각하고 풀었던 문제이다. 일단 죄수 두 명 중 한 명이 문을 이미 열었다면 그 문은 다른 죄수가 열지 않아도 되는데
이 처리를 어떻게 해야하나 고민했다.

문제를 해결한 방법은
주어진 입력의 바깥 부분을 모두 '.'으로 채웠다. 0,0에서 bfs를 출발하여 임의의 방문 배열을 주고 해당 좌표마다 문을 얼마나 깨고 갔는지를 체크했다.
그리고 두 죄수의 좌표에서 bfs를 실행했고 위와 똑같이 방문배열에 문을 깨고 간 만큼을 입력했다.

그럼 총 이차원 방문 배열이 3개가 나온다. 이 3개를 모두 더한 후 최솟값을 찾았다.
하지만 문이 위치한 곳이라면 -2를 해줬다. 두 죄수 + 외부에서 출발한 임의의 사람 이 동시에 다 같이 문을 연것이기 때문에 -2를 해줬다.

[백준 2665] 미로만들기

[ 백준 2665 : 미로만들기 ]

간단한 bfs문제
벽을 최소한으로 부수고 목적지까지 가면된다.

기본 bfs처럼 상하좌우를 탐색한 후 만약 검은방인 0 이라면 큐에 현재 벽을 부순 개수+1 을 push 하고 흰방인 1 이라면 그대로 push를 하면 된다.
방문했는지 안했는지를 체크하기 위해 int형 이차원 배열을 이용해 그 자리까지 벽을 부수고 온 갯수를 집어 넣었다.
만약
다음 가야할 좌표의 방문 이차원 배열의 수가 현재 벽을 부순 개수보다 크다면 이동을 하고 작다면 해당 좌표로 이동하지 않으면 된다.

[백준 1406] 에디터

[ 백준 1406 : 에디터 ]

스택개념을 안다면 다들 쉽게 풀 수 있는 문제가 몇 가지 있는데
대표적으로 괄호 판단 하는 문제나 사칙연산문제들 그리고 메모장문제가 있다.

내각 메모장 문제라고 하는 문제들은 스택을 두 개 써서 커서를 움직이면서 중간에 글자를 삽입하고 지우고 할 수 있는 문제들이다.
링크드리스트로도 풀 수 있겠지만 0.3초의 짧은 제한시간인만큼 계속해서 커서를 옮기고 최대 글자 수가 60만이기 때문에 무리가 있다.

일단 스택을 두 개(ST1, ST2) 를 쓴다고 가정하면 커서의 위치는 ST1의 사이즈가 된다.

기본 개념은
글자를 단순히 추가할때는 ST1에 푸쉬를 한다. 그리고 커서를 왼쪽으로 옮길때는 ST1의 TOP을 ST2로 푸쉬한다. 그리고 ST1을 POP한다.
또한 커서를 오른쪽으로 옮길때는 반대로 하면되고 해당 커서에서 글자를 삭제할때는 ST1에서 POP하면된다.

그리고 총 문자를 출력할때는 ST1의 인덱스 0부터 ST1.SIZE()까지 ST2.SIZE()-1부터 ST2인덱스0까지 출력하면 된다.

O(N)으로 0.3초안에 들어오니 충분히 풀만하다.

괄호판단 문제나 메모장문제는 다 비슷비슷한 유형이기때문에 한 번 제대로 풀어보면 다음엔 수월하게 풀 수 있다.

[백준 16137] 견우와 직녀

[ 백준 16137 : 견우와 직녀 ]

오랜만에 BFS문제를 풀어본것같다. 사실 문제를 읽으면서도 이게 BFS맞겠지 하고 풀었다.
왠만하면 BFS와 DFS같은 문제들은 바로 음 이렇게 풀어야지 하는데 이문제는 한글해석이 너무 어려웠다... 영문을 번역한것도 아닌데 무튼 좀 이상했다ㅋㅋㅋㅋㅋㅋ

첫번째로는 말이 이상하다.

이렇게 되면, 까치와 까마귀에게 굉장히 미안하면서도 민망해지기 때문에 견우는 오작교를 두 번 연속으로 건너는 일은 피하려고 한다.

이런 상황에서도 까마귀와 까치는 견우와 직녀를 도와주고 싶었기 때문에, 견우가 원하는 다리에서 주기가 M 분인 다리를 하나 더 놓아주겠다고 한다. 다만, 아래와 같이 절벽이 가로와 세로로 교차하는 경우에는 까마귀와 까치가 다리를 만들어 줄 수 없다고 한다.

내가 이상한건지는 모르겠는데
두번 연속으로 건너는 일은 피하려고한다. -> 이런 상황에도 까치와 까마귀는 도와준단다
-> 원하는 다리에서 주기M분인 다리를 만들어준다 -> 절벽이 가로세로 교차시엔 안만들어준다.

어떤때는 다리라고하고 어떤때는 오작교라고 하고 처음에 푼게 틀렸다고 나와서 두개가 다른건줄 알았다.

1.그리고 다리에서 M인 다리를 하나 더 놓아준다는게 이미 초기 인풋에 있는 다리에서 이어지는 다리를 만들어준다는 건가????? 이렇게 생각했고
5 5
1 1  0 1   1
2 1  1 0 20
0 4  1 0   0
0 0  1 1   1
0 1  1 1   1

2.절벽이 가로와 세로로 교차하는 경우에는 다리를 만들어주지 못한다했으니
5 5
1 1  0 1   1
2 0  1 0 20
0 4  1 0   0
0 0  1 1   1
0 1  1 1   1

이런 경우에  는 (1행,2열)의 0에는 다리를 만들수있다는거라 생각했고


또 뭔가 빠진게 견우가 움직이는 시간이다.
견우는 상하좌우 로만 움직일 수 있고 한 칸 이동하는데 1의 시간이 소요된다는 점도 빠져있다. 그래서 1-> 1 이동은 0초인건가????
별의별 생각을 다했는데
방문했는지 안했는지 처리를 잘못해서 계속 틀리는 거였다.

결론으로는 1. 그림은 못만든다. 무조건 만들어준 다리든 원래 있던 다리든 오작교든
다리에서 다리로는 못가게 처리했고
2. 그림은 만들수있게했다. 절벽만 크로스 될때 다리를 못만들게 처리헸다.

맵을 인풋받고 초기에 절벽이 크로스 되는 지점들을 모두 -1로 만들었다.


이제 bfs를 돌렸는데
Queue에 넣을 원소로는 x좌표,y좌표,현재까지의 시간, 만든 다리를 건넜는지 체크

상하좌우를 살펴보면서
1. 현재 1에 있을때 다음이 1이고 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입
2. 현재 1에 있을때 다음이 0이고 만든 다리를 안건넜다면 배수 시간으로 큐 삽입
3. 현재 0에 있을때 다음은 1이고 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입
4. 현재 1에 있을때 다음이 2 이상이고 배수 시간으로 큐 삽입
5. 현재 2 이상이고 다음이 1일때 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입

[백준 2501] 약수 구하기

[ 백준 2501 : 약수 구하기 ]


한 자연수의 약수를 구한 후 약수 중 k번째로 작은 수를 구하면된다.
일단 약수 구하는 식은 뻔하고 약수나 소수 구하는 소스는 이전에도 많이 게시했었는데 그래도 다시 한번 로직을 올려본다.

-약수 구하는 로직-
약수를 구할 자연수 N에 대해서 총 시간 복잡도는 SQRT(N) [N 제곱근] 이 걸린다.
자명한 시간복잡도인데 16라는 수를 생각해보자.
16의 약수 = 1 2 4 8 16 이렇게 나오는데
16은 1로 나누어떨어지고 1로 나눌때의 몫이다. 이렇게 1과 16이 구해진다.
16은 2로 나누어떨어지고 2로 나눌때의 몫은 8이다. 이렇게 2과 8이 구해진다.
16은 4로 나누어떨어지고 4로 나눌때의 몫은 4이다. 이렇게 4가 구해진다.
이제 4보다 큰 수는 없다. 4보다 큰수는 이미 4보다 작은수로 나눴을때의 몫으로 구해졌기때문이다.
-끝-

그럼 이런 방식으로 약수를 모두 구한다. N의 범위가 1만이므로 O(100)안에 구해지니까 시간은 통과
그리고 소팅을 한다. 그럼 최악에 100*log100

그 후 k-1번째 인덱스의 수를 출력하면된다.

[백준 3273] 두 수의 합

[ 백준 3273 : 두 수의 합 ]

이번 주 토요일 ICPC인터넷 예선이 있어서 조금 급하게 닥치는대로 눈에 보이는 문제들을 푸는중...
근데 어려운건 좀 풀기가 부담스러워서 ㅋㅋㅋㅋㅋ쉬운것들만 한번 올려야..지..

수열의 크기가 주어지고 수열 그리고 한 정수가 주어진다. 그리고 조건을 만족하는 쌍의 개수를 출력하는 문제
조건은 두개의 수를 더해서 입력으로 주어진 정수가 되는것이다.

일단 N의 크기가 50만이고 만약 한개씩 대입해서 본다고 해도 최악에 50!이라는 범위가 나와버린다.

그래서 NlogN 으로 풀었는데 먼저 정렬을 한다.
그리고 한 숫자를 기준으로 그다음 인덱스를 Left 수열 크기-1를 Right 로 잡고 이분탐색으로 일치하는 쌍이 나올때마다 출력변수+1씩해준다.

그럼 총
logN + NlogN이므로 제한시간안에 충분히 들어올 수 있당.

[백준 13459] 구슬탈출

[ 백준 13459 : 구슬탈출 ]

구슬탈출2 문제와 똑같은 문제... 삼성 역량테스트 보기 전 연습으로 풀면 좋을 듯한 문제다.
로직은 같고 이번엔 큐를 이용해서 풀었다. 그리고 vi사차원 배열 변수를 이용해 중복된 빨간공과 파란공의 위치가 있다면
방문하지 않아 시간을 줄여보았다.

기본 로직은
1. 빨간공을 움직인다.
1-1. 만약 벽에 부딪히면
1-1-1. 파란공을 움직인다.
1-1-1-1. 파란공이 벽에 부딪힌다. -> 큐에 푸쉬
1-1-1-2. 파란공이 구멍에 빠진다. -> 끝냄
1-2. 만약 파란공에 부딪히면
1-2-1. 파란공을 움직인다.
1-2-1-1. 파란공이 벽에 부딪힌다.
1-2-1-2. 빨간공을 파란공 옆에 붙힌다. -> 큐에 푸쉬
1-2-1-3. 파란공이 구멍에 빠진다. -> 끝냄
1-3. 만약 구멍에 빠지면
1-3-1. 파란공을 움직인다.
1-3-1-1. 파란공이 벽에 부딪힌다. -> 1을 출력하고 프로그램 종료
1-3-1-2. 파란공이 구멍에 빠진다. -> 끝냄

이런식으로 구현했다.

[백준 1765] 닭싸움 팀 정하기

[ 백준 1765 : 닭싸움 팀 정하기 ]


조금 억지스럽게 푼것같은 문제
처음에 문제를 어떻게 풀어야 할지 계속 생각하다가 그냥 완탐으로 풀었다.
문제는 재귀로 풀까 반복문으로 풀까 망설이다가 그냥 큐로 풀었다.

문제가 좀 간단한데 해석하는데 좀 걸렸다. 요즘엔 한국어도 해석이 어렵다...
무튼
F로 나온 사람들은 일단 모두 같은 팀이다.
E인 사람은 그러니까, 원수의 원수는 같은팀이고 이 사람의 친구들도 같은팀이다.
이렇게 생각하면 쉽게 풀리는데

1. 일단 로직은 원수인 사이들을 모두 벡터(E)에 넣고 친구인 사이를 모두 벡터에 집어넣는다(F).
2. 사람 1번부터 N번까지 탐색을 할텐데 만약 현재 살펴봐야할 사람이 이미 팀에 소속되어 있으면 그냥 건너 뛴다.
3. 만약 아무 팀에도 들어가 있지 않는다면 현재 만들어진 팀+1 팀에 들어간다. 그리고 BFS를 돈다.
4. 일단 이 사람 (X) 의 친구들의 친구들 무튼 친구랑 친구관계인 사람들은 모두 내 팀이니 전부 같은 팀으로 넣는다.
5. 원수인 사람은 일단 큐에 집어넣고 첫번째 원수로 표시를 해준다.
6. 첫번째 원수의 원수들(Y)은 모두 현재X의 팀이니 X의 팀으로 표시해 준 후 Y를 큐에 집어넣는다. 물론 Y부터는 친구들을 볼거다. Y의 원수는 건너뛴다.

이런식으로 풀었는데 처음에 한 번 틀렸다. 틀린 이유는 처음에 문제에 나온대로 친구의 친구까지만 같은 팀으로 표시했기 때문이다.
문제를 계속 보다가 결국 이해 했고 친구의 친구의 친구의 친구의....~~ 모두 X의 팀이라고 이해했고 고치니까 맞았다.

코드를 참고하자.

[백준 14569] 시간표 짜기

[ 백준 14569 : 시간표 짜기 ]

으음.. 완전탐색으로 풀긴했는데 이게 정해인지는 확실하지않다.
그런데 AC가 나와서 조금 당황했다.

일단 로직은 INT형 이차원 배열을 만들어 체크를 한다.
[과목번호][수업시간] 이런식으로 그리고 [과목번호][0]과 [과목번호][51]에는 수업시간의 수를 집어넣는다.

이제 M에서 입력을 받으면서 비어있는 교시를 입력할때마다 1~N까지의 이차원 배열을 보고 체크를 한 후 [51]-- 를 해준다.
[과목번호][51] == 0 이되면 이 수업은 들을 수 있다고 판단하면된다.


사실 여기서 조금 이상했다.
학생수는 M 즉, 10000명이다. 그럼 일단 시간복잡도가 최악에 O(10000)이된다. 여기에
비어있는 교시 갯수가 50이 들어오니 O(10000 * 50) 그리고 한번 입력할때마다 1000개의 수업을 살펴보게되면 O(10000*50*1000) 으로 이미 1초를 넘기는것같았는데
어째선지 시간은 1초는커녕 0.02초가 나왔다;;;

무튼 AC를 받았는데 다른 풀이법으로 풀어보도록 생각해봐야할 문제.

[백준 1719] 택배

[ 백준 1719 : 택배 ]

다익스트라 기본 문제이다. 다익스트라 알고리즘을 구현 할 줄만 알면 풀 수 있는데 조금 다른점이있다.
한 좌표에서 목표 좌표까지의 최단 경로의 값을 뽑는게 아니라
한 좌표에서 최단 경로로 갈 때 가장 먼저 가야하는 좌표를 출력하는 것이다.

평소 나는 다익스트라 알고리즘 문제를 풀 때 항상 푸는 형식이 있는데 이 상태에서 배열 한 개만 더 선언해주면 되었다.
보통 다익스트라로 최단 거리를 뽑을때 dist라는 배열과 우선순위 큐를 이용하는데

우선순위큐의 가장 위에 있는 cost와 dist에 저장된 cost의 값을 비교해 더 적은 값의 cost로 좌표를 갈 수 있다면
dist의 cost를 갱신해주는 방식이다.
이때 우선순위큐에 한 개의 파라미터를 더 넣었다.
이 변수는 출발점에서 한 번만 이동할때의 값을 넣어준다.

만약 현재 탐색해야하는 좌표가 출발점에서 두번 이상 지나왔다면 더이상 우선순위 큐에 이 변수값을 변화시키지 않는다.
하지만 dist가 갱신될때는 변수값을 변화시킨다...

그림으로 설명하고 싶은데.... 어떻게 해야할지 모르겠다..위의 말이 잘이해가 안간다면 소스를 보는것을 추천한다.

[백준 1652] 누울 자리를 찾아라

[ 백준 1652 : 누울 자리를 찾아라 ]

간단한 완전탐색문제

한 좌표를 기준으로 오른쪽으로 2칸이상 '.' 이거나 아래로 2칸이상 '.'이면 갯수를 세어주면된다.
그리고 한번 가로로 또는 세로로 2칸이상이었던 좌표들ㄹ은 모두 체크해서 나중에 방문하지 않으면된다.

입력 문자열만으로 충분히 방문했는지 체크할 수 있겠지만 너무 귀찮은 과정이므로 생략하고 그냥 방문 이차원배열을 선언해
1번비트에 체크 될때는 세로로 방문한것으로 2번비트에 체크 할때는 가로로 두 비트가 모두 체크되어있다면 건너뛰는 형식으로 구현시켰다.

2번비트까지만 사용하므로 굳이 int를 쓰지않고 char로 이차원배열을 선언했고 갯수를 세어주는 변수(cnt1,cnt2)도
아무리 커봤자 100이하이므로 char로 선언했다.


VISIBLE CONTENT HERE

[백준 1806] 부분합

[ 백준 1806 : 부분합 ]

간만에 손도 풀고 감도 익힐겸 사이트에 들어갔는데 그냥 먼저 보이는 문제 하나 집어서 풀었다.
이 문제를 처음 읽고 메모이제이션해놓으면 편할것 같은데.. 생각하고 일단 바로 메모를 해놨다.
DP라는 배열에 현재까지 배열의 합을 저장해 놓고 0번 인덱스 부터 N번째 인덱스까지 이분탐색으로 S를 넘는 값이 있는지를 탐색했다.

그리고 조금이나마 시간을 아껴보려고 배열을 입력받을때 S를 넘는 값이 있으면 바로 1을 출력한 뒤 프로그램을 종료시켰다.
그렇지 않다면
로직은 위에서 말한대로

0번 인덱스부터 N번째 인덱스를 탐색한다.
만약 5번 인덱스를 탐색할때
이분탐색으로 0번부터 5번을 L과 R로 정한 후 MID=(L+R)/2값을 살펴본다.
DP[5] - DP[MID] 이런식으로 하면 MID부터 현재 인덱스까지의 합이 몇인지 쉽게나온다.

간단한 이분탐색 응용문제라고 생각한다.

[백준 2042] 구간 합 구하기

[ 백준 2042 : 구간 합 구하기 ]

처음 문제를 보고 세그먼트 트리로 풀어야겠네 이런 생각을 하게된다.
만약 세그먼트트리를 모른다면 <백준 세그먼트 트리 설명> 해당 링크에 엄청나게 자세히 설명되있다.

어제 인덱스트리라는 로직을 새롭게 배웠는데 너무 인상깊어서 인덱스 트리 방식으로 풀어봤다.
사실 세그먼트 트리 코드가 왠만하면 위의 설명에 나온 코드나 흔히 말하는 종만북 이라는 책에 나온대로 설계하고 구현한다.
엄청 복잡(사실 복잡하진 않다.) 하고 코드가 매우 길다.

인터넷에서도 세그먼트트리 알고리즘을 사용하는 문제 풀이를 찾아보면 거의 비슷비슷하게 나와있는것을 알 수 있다.
벡터로다가 사이즈 먼저 설정하고 초기화 시키고~ 사실 인덱스 트리도 똑같은 방법이긴 한데 조금 더 쉽게 구현할 수 있어서 적어본다.

일단 기본 로직은 세그먼트 트리와 비슷하다. 초기화를 먼저 시키는데 이때 배열의 사이즈를 임의대로 n*4를 한다.

n이 10이라고 가정하면
가장 밑단에 들어가는 데이터 10개의 공간이 필요하다. 이건 입력으로 주어지는 배열과 사이즈가 같다.
그 위 층으로는 두개씩 묶어 부모이자 해당 구간의 쿼리를 저장 할 공간 5개가 필요해다.
그 위 층은 또 두개씩 묶어 3개가 필요한데 범위 10을 넘으니 임의로 0을 저장한다.
이런식으로 하면 총 25개가 필요한데 넉넉하게 그냥 4배를 잡는다.

트리 사이즈를 잡았다면 이제 초기화를 시켜준다. 초기 값은 트리사이즈-n 부터 트리사이즈까지 입력 배열들이 들어간다.
그리고 /2를 하면서 해당 공간에 문제에서 요구하는 쿼리값을 집어넣는다. 만약 쿼리가 구간의 합을 구하는 것이라면
트리의 인덱스를 /2하면서 +입력배열[i]를 해주는 식으로
그럼 초기화는 끝난다.

업데이트는 트리사이즈 - N + (업데이트 하는 인덱스)부터 /2를 해가면서 트리의 값을 수정해준다. 정말 간단하다.

쿼리함수는 조금 복잡한데
흔히 알려진 세그먼트 트리 구현하는 것보다는 간단하다. 기본 로직은

구간 시작 인덱스 IDX1 , 구간 끝 인덱스 IDX2, 결과값 RET 이라고 가정해본다.
그럼 IDX1 = 트리사이즈 - N +IDX1이 트리의 가장 밑단, 입력배열의 값이된다.

while(IDX1<=IDX2) IDX1이 홀수라면 해당 트리의 값을 RET에 갱신시킨다. 그리고 IDX1을 +1 해준다. IDX2가 짝수라면 해당 트리의 값을 RET에 갱신시킨다. IDX2를 -1 해준다. IDX1 과 IDX2를 /2해준다. 사실 배열을 그림으로 그려서 이해하면 왜 이렇게 하는지 알게되는데 직접 그려보고 이해하면 진짜 인덱스트리는 이제 자기것이라고 보면될 것 같다. 이런식으로 구간합구하기 문제를 풀었는데 처음에 트리 사이즈를 잘못구해 몇 번을 틀렸는지 모르겠다... 비슷한 문제로 [최소값] 와 엄청나게 많으니 풀어보길 추천한다.

[백준 9663] N-Queen

[ 백준 9663 : N-Queen ]

N퀸문제는 너무나도 유명한 문제라서 인터넷에도 엄청나게 많이 풀이법들이 있다.
가장 직관적이고 그나마 접근하기 쉽게 풀었는데

만약 이 문제를 한번에 풀이법을 생각하지 못한다면 이것만 알면된다.
퀸은 모든 방향으로 공격이 가능하니 한 행 또는 한 열에 퀸은 무조건 한 개씩만 존재한다.
이것만 이용하면 쉽게 풀린다.

일단 퀸은 대각선과 가로세로에 모두 공격할 수 있다. 그러므로 한 좌표에 퀸이 놓아진다면 해당 행과 열에는 절대 퀸을 놓을 수 없다.
따라서 한 행에 한개씩 놓고 그다음 행에 0~N열까지 한번씩 놔보는 식으로 구현이가능하다.

N이 15 미만이기 때문에 최악의 경우 14(행)*14(열)충분히 10초이내에 들 수 있다.

나는 백트래킹을 통해 사실 그냥 완탐이지만 주어진 맵을 다시 그 전 상태로 돌리기를 위해 재귀를 이용했다.
해당 좌표에 퀸을 놓을 수 있는지를 알아보는 방법으로는 INT형 이차원 배열을 이용했는데
한 곳에 퀸을 놓고 그 퀸이 공격할 수 있는 모든 좌표에 +1씩해준다. 그 전상태로 돌아갈때는 -1을 해주는데
이 이유로는 총 두개의 퀸이 같은 좌표를 공격할 수 있다고 했을때 어떤 하나의 퀸이 없는 상태가 되더라도 해당 좌표에 퀸을 놓지 못하게 하기 위해서이다.

[백준 1697] 숨바꼭질

[ 백준 1697 : 숨바꼭질 ]

문제에 주어진대로 구현하면된다.
수빈이는 x위치일때 x+1 또는 x-1 또는 2*x의 위치로 1초마다 이동할 수 있다.
그럼 BFS탐색을 해준다면 모든 방문을 해주면서 동생이 있는 위치 K에 도달하게 할 수 있다.
그때의 시간이 가장 빠른 시간임이 보장된다.